package com.jjlin.chapter_3;



import java.util.*;
public class CD168 {
    //二叉树节点
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static Node createBinaryTree(int[][] nums, int root){
        HashMap<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < nums.length; ++i){
            map.putIfAbsent(nums[i][0], new Node(nums[i][0]));
            if(nums[i][1] != 0){
                map.putIfAbsent(nums[i][1], new Node(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                map.putIfAbsent(nums[i][2], new Node(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //二叉树的按层打印
    public static void printByLevel(Node root){
        if(root == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            int size = queue.size();
            sb.append("Level " + level + " : ");
            for(int i = 0; i < size; i++){
                Node cur = queue.poll();
                sb.append(cur.val + (i != size - 1 ? " " : "\n"));
                if(cur.left != null)
                    queue.offer(cur.left);
                if(cur.right != null)
                    queue.offer(cur.right);
            }
            level++;
        }
        System.out.print(sb.toString());//注意这里不要换两次行！！！
    }

    //二叉树的按ZigZig打印
    public static void printByZigZig(Node root){
        if(root == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        boolean flag = true;
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            int size = queue.size();
            sb.append("Level " + level + " from ");
            sb.append(flag ? "left to right: " : "right to left: ");
            if(flag){
                for(int i = 0; i < size; i++){
                    Node cur = queue.poll();
                    sb.append(cur.val + (i != size - 1 ? " " : "\n"));
                    if(cur.left != null)
                        queue.offer(cur.left);
                    if(cur.right != null)
                        queue.offer(cur.right);
                }
            }else{
                Stack<Node> stack = new Stack<>();
                for(int i = 0; i < size; ++i){
                    Node cur = queue.poll();
                    if(cur.left != null)
                        queue.offer(cur.left);
                    if(cur.right != null)
                        queue.offer(cur.right);
                    stack.push(cur);
                }
                while(!stack.isEmpty())
                    sb.append(stack.pop().val + (--size != 0 ? " " : "\n"));
            }
            flag = !flag;
            level++;
        }
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < 3; ++j)
                nums[i][j] = sc.nextInt();
        Node head = createBinaryTree(nums, root);
        printByLevel(head);
        printByZigZig(head);
    }
}

